1. Field of the Invention
This invention relates to use of an expanded data structure (referred to herein as M-trie Plus) for packet processing.
2. Related Art
In a computer network, a router or switch operates to receive messages at its input interfaces and to send messages from its output interfaces. In performing these tasks, the router or switch must generally determine which output interface (if any) is appropriate for forwarding the message. When making this determination, the router or switch is responsive to the destination IP address (for multicast packets, the router or switch is also responsive to the source IP address). Similarly, the router or switch can also be responsive to the source IP address for policy routing.
A first method of identifying an outbound interface for a particular packet is to look up the IP address on the packet in a TRIE data structure, as described in the Incorporated Disclosures.
In a known system described in the Incorporated Disclosures, the router or switch uses each of the four bytes of the destination IP address to perform a lookup in a branching table having a set of up to 256 possible branching entries in a TRIE data structure, terminating in a leaf node in the TRIE upon or before having performed the lookup for each byte of the destination IP address. Thus, it is possible to determine an appropriate output interface for the destination IP address by going through no more than four cycles on the TRIE before coming to a leaf node that specifies the actual handling instructions for the packet.
One drawback to TRIE data structure processing is that it is limited to processing the destination IP address. It would be desirable to expand on this so as to single out other aspects of the packet header beyond the four bytes specifying the destination IP address.
A second drawback to the use of a TRIE for lookups is that access control list (ACL) processing remains separate from routing. In some embodiments, ACL processing is driven by software. Since this process is relatively slow when compared to high-speed routers, ACL processing slows the overall rate at which data packets are forwarded. Depending upon the length of the ACL criteria, router speeds can drop 70% or more.
A third drawback to use of a TRIE is that the nodes and leaves of the TRIE generally do not provide adequate information to direct multicast routing.
Accordingly, it would be desirable to provide an improved technique for looking up information contained in a packet header relevant to routing and access control. This is achieved in an embodiment of the invention which is a novel and nonobvious expansion on an expanded TRIE structure, herein called an M-trie Plus data structure. In addition to providing unicast routing and access control list processing, an M-trie Plus data structure can be used with techniques for multicast routing, ACL processing, CoS (class of service) processing, QoS (quality of service) processing, and the like.